from src.com.kaizen.leet136 import *

'''
给定一个非空整数数组，除了某个元素只出现一次以外，其余每个元素均出现两次。找出那个只出现了一次的元素。
<p>
说明：
<p>
你的算法应该具有线性时间复杂度。 你可以不使用额外空间来实现吗？

 * 示例 1:
 输入: [2,2,1]
 输出: 1
 
 * 示例 2:
 输入: [4,1,2,1,2]
 输出: 4
 通过次数185,414提交次数277,338
'''

#方法一  列表操作
'''
创建一个列表n_list
用i遍历nums，如果n_list中不存在i值，则添加i值
如果n_list中存在i值，则把该值从列表中移除
最后输出只输出过一次的值
'''

class Solution:
    def singleNumber(self,nums):
        n_list=[]
        for i in nums:
            if i not in n_list:
                n_list.append(i)
            else:
                n_list.remove(i)
        return n_list.pop()     #pop（）：移除列表中的一个元素（默认最后一个元素），并返回该元素值


#方法二 哈希表
'''
1、遍历 nums 中的所有元素并建立键/值对。
2、返回只出现一次的元素。
'''
from collections import defaultdict
class Solution:
    def singleNumber(self, nums):
        hash_table = defaultdict(int)
        for i in nums:
            hash_table[i] += 1

        for i in hash_table:
            if hash_table[i] == 1:
                return i